Caches are generally small, fast storage buffers employable to store information, such as code or data, in order for a processing device to more quickly and efficiently have access to the information. Typically, it is faster for the processing device to read the smaller memory of the cache than to read a main memory. With the rapid increase of intensive computational requirements, the importance of caches in computing systems will only increase.
Typically, when a cache does not have selected information, replacement logic will be employed to select the replacement candidate. The replacement logic can utilize the LRU function or the MRU function. One form of cache that employs the LRU and MRU functions is an “n-way set associative” cache. An “n-way set associative” cache with S sets has n cache locations in each set. Cache line b is mapped to set “b mod S” and may be stored in any of the n locations in that set. A partitioned n-way set associative cache stores the cache line in the partition. To determine whether block b is in the cache, set “b ” mod “S” is searched associatively for the matching tag.
The LRU function determines the least recently used way within the cache of a given set. Then, the cache replaces the information targeted by the LRU function with the newer information. This cache line replacement allows the processor to quickly access the selected information the next time this information is requested. Furthermore, this replacement also increases the chances of the processor finding associated information within the cache, as the replaced way cache data can have temporal locality.
In other circumstances, a most recently used (MRU) function can be used. The MRU function determines the most recently used way in a cache. The MRU can be used for graphics images, for instance, when information is to be used once, then discarded.
Ways of cache can be partitioned. A partition is generally defined as a grouping of ways in a cache that shares associated update and replacement strategies. For instance, ways one, two and three could be updated under certain circumstances, and ways four, five, six, seven, and eight are updated under other circumstances, such as correspondence to a given address range as indicated by the address tag.
However, there are problems when employing conventional LRU or MRU functionality with a partitioned cache. For instance, in the LRU or MRU in conventional systems, a 24 bit LRU or MRU key can be used. However, to update the LRU or MRU key, the 24 bit key is read, rearranged and saved in the rewritten form. This is a time consuming and processing intensive process.
Therefore, what is needed is a cache partition management that overcomes the limitations of conventional cache partition management.